package com.objcat.playground.leetcode;

/**
 * description: Solution22 <br>
 * date: 2022/3/15 12:30 PM <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Solution26 {

    /**
     * 首先根据题意我们可以写出下面算法
     * 1,如果root为空, 默认就是有效的二叉搜索树
     * 2.如果不满足条件 即左边的值小于本身值 右边的值大于本身值 就返回false
     * 算法的核心其实不难 就是判断值的范围
     * 但是我们忽略了一个问题 就是只判断了当前节点的范围 没有考虑之前节点的范围
     *
     *     3
     *    / \
     *   1   5
     *      /  \
     *    (2)   6
     *
     *  我们可以看到 括号里的数字(2) 是不符合规则的 虽然它小于5 但是它也要大于3 因为3右边的节点都要比本身大 所以括号里应该是4才符合条件
     *  所以我们的算法是不正确的
     *
     *       3
     *      / \
     *     2   5
     *    /  \
     *   1   (5)
     *
     *  相反的 我们也可以看到括号里的数字(5) 也是不符合规则的 虽然它大于2 但是它也要小于3
     *
     */

    public boolean isValidBST2(TreeNode root) {

        if (root == null) {
            // 如果root为空, 默认是有效的二叉搜索树返回true
            return true;
        } else if ((root.left != null && root.left.val >= root.val) || (root.right != null && root.right.val <= root.val)) {
            // 不符合条件就返回false
            return false;
        }

        // 如果左节点和右节点都满足说明是有效的二叉搜索树
        return isValidBST2(root.left) && isValidBST2(root.right);
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minValue, long maxValue) {
        if (root == null) {
            return true;
        }

        if (root.val >= maxValue || root.val <= minValue) {
            return false;
        }
        return isValidBST(root.left, minValue, root.val) && isValidBST(root.right, root.val, maxValue);
    }

    public static void main(String[] args) throws InterruptedException {

        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;

        Solution26 solution26 = new Solution26();
        System.out.println(solution26.isValidBST(node1));
    }
}
